import java.util.Arrays;
import java.util.LinkedList;
import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class training {
    //你可以安排的最多任务数目
    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        int n = tasks.length, m = workers.length;
        Arrays.sort(tasks);
        Arrays.sort(workers);

        int res = 0;
        // 二分
        int left = 1, right = Math.min(n, m);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(tasks, workers, pills, strength, mid)) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    // 检测是否能完成 t 个任务
    public boolean check(int[] tasks, int[] workers, int pills, int strength, int t) {
        int n = tasks.length, m = workers.length;
        List<Integer> workerList = new LinkedList<>();
        // 只取最大的t个工人
        for (int i = m - 1; i >= (m - t); i--) {
            workerList.addFirst(workers[i]);
        }
        // 取最小值的t个任务，并且从大到小遍历任务
        for (int i = t - 1; i >= 0; i--) {
            int taskValue = tasks[i];
            // 如果有工人的值大于等于该任务的值，则不使用药丸，并使用值最大的工人完成该任务
            if (workerList.getLast() >= taskValue) {
                workerList.removeLast();
            }
            // 如果所有工人的值都小于最大值任务，则使用药丸让一名工人完成，并且一定让小的工人完成
            else {
                if (pills <= 0) return false;
                boolean canFinshed = false;
                // 从小到大遍历工人，找到最小的吃药能够完成任务的工人
                // for (int j = 0; j <= workerList.size() - 1; j++) {
                //     if ((workerList.get(j) + strength) >= taskValue) {
                //         workerList.remove(j);
                //         pills--;
                //         canFinshed = true;
                //         break;
                //     }
                // }
                // workerList 是从小到大
                // 优化，二分查找
                int left = 0, right = workerList.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if ((workerList.get(mid) + strength) >= taskValue) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                if (left < workerList.size() && (workerList.get(left) + strength) >= taskValue) {
                    workerList.remove(left);
                    pills--;
                    canFinshed = true;
                }
                if (!canFinshed) {
                    return false;
                }
            }
        }
        return true;
    }
}
